#define _CRT_SECURE_NO_WARNINGS 1
#include "Tree.h"
#include "duilie.h"

TreeNode* CreatBinaryTree()
{
	TreeNode* node1 = BuyNewNode(1);
	TreeNode* node2 = BuyNewNode(2);
	TreeNode* node3 = BuyNewNode(3);
	TreeNode* node4 = BuyNewNode(4);
	TreeNode* node5 = BuyNewNode(5);
	TreeNode* node6 = BuyNewNode(6);
	TreeNode* node7 = BuyNewNode(7);
	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node2->right = node5;
	node3->left = node6;
	node3->right = node7;
	return node1;
}

TreeNode* BuyNewNode(dataType x)
{
	TreeNode* ret = (TreeNode*)malloc(sizeof(TreeNode));
	if (ret == NULL) {
		perror("malloc");
		return NULL;
	}
	ret->data = x;
	ret->left = ret->right = NULL;
	return ret;
}

void PrevOrder(TreeNode* root)
{
	if (root == NULL) return;
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

void InOrder(TreeNode* root)
{
	if (root == NULL) return;
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

void HouOrder(TreeNode* root)
{
	if (root == NULL) return;
	HouOrder(root->left);
	HouOrder(root->right);
	printf("%d ", root->data);
}

int TreeSize(TreeNode* root)
{
	if (root == NULL) return 0;
	return 1 + TreeSize(root->left) + TreeSize(root->right);
}

int TreeYeZiSize(TreeNode* root)
{
	if (root == NULL) return 0;
	if (root->left == NULL && root->right == NULL) return 1;
	return TreeYeZiSize(root->left) + TreeYeZiSize(root->right);
}

int TreeHeight(TreeNode* root)
{
	if (root == NULL) return 0;
	int left = TreeHeight(root->left);
	int right = TreeHeight(root->right);
	return left > right ? left + 1 : right + 1;
}

int TreeSizeByK(TreeNode* root, int k)
{
	if (root == NULL) return 0;
	if (k == 1) return 1;
	return TreeSizeByK(root->left, k - 1) + TreeSizeByK(root->right, k - 1);
}

TreeNode* BinaryTreeFind(TreeNode* root, dataType x)
{
	if (root == NULL) return NULL;
	if (root->data == x) return root;
	TreeNode* tmp = BinaryTreeFind(root->left, x);
	if (tmp != NULL)
		return tmp;
	tmp = BinaryTreeFind(root->right, x);
	if (tmp != NULL)
		return tmp;
	return NULL;

}

void BinaryTreeDestory(TreeNode** root)
{
	if ((*root) == NULL) return;
	BinaryTreeDestory(&(*root)->left);
	BinaryTreeDestory(&(*root)->right);
	free(*root);
	*root = NULL;
}

int BinaryTreeComplete(TreeNode* root)
{
	if (root == NULL) return 1;
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		TreeNode* tmp = QueueFront(&q);
		QueuePop(&q);
		if (tmp == NULL)
			break;
		QueuePush(&q, tmp->left);
		QueuePush(&q, tmp->right);
	}
	while (!QueueEmpty(&q)) {
		TreeNode* tmp = QueueFront(&q);
		QueuePop(&q);
		if (tmp != NULL)
		{
			QueueDestroy(&q);
			return 0;
		}			
	}
	QueueDestroy(&q);
	return 1;
}

void BinaryTreeLevelOrder(TreeNode* root)
{
	if (root == NULL) return;
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		TreeNode* tmp = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", tmp->data);
		if (tmp->left != NULL)
			QueuePush(&q, tmp->left);
		if (tmp->right != NULL)
			QueuePush(&q, tmp->right);
	}
	QueueDestroy(&q);
}

TreeNode* BinaryTreeCreate(dataType* a, int n, int* pi)
{
	if (a == NULL) return NULL;
	if (!(*pi <= n)) return NULL;
	TreeNode* root = NULL;
	if (a[*pi] == '\0') return NULL;
	if (a[*pi] != '#') {
		root = BuyNewNode(a[(*pi)++]);
	}
	else {
		(*pi)++;
		return NULL;
	}
	root->left = BinaryTreeCreate(a, n, pi);
	root->right = BinaryTreeCreate(a, n, pi);
	return root;
}

//TreeNode* chuangJian(char* arr, int* pi)
//{
//	if (arr == NULL) return NULL;
//	TreeNode* root = NULL;
//	//if (arr[*pi] == '\0') return NULL;
//	if (arr[*pi] != '#') {
//		root = BuyNewNode(arr[(*pi)++]);
//	}
//	else {
//		(*pi)++;
//		return NULL;
//	}
//	root->left = chuangJian(arr, pi);
//	root->right = chuangJian(arr, pi);
//	return root;
//}